public class Test2 {
    //leetcode 从中序和后序遍历序列构建二叉树
    //https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=problem-list-v2&envId=tree
    int index;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = postorder.length - 1;
        return buildTreeChild(inorder,postorder,0,index);
    }

    private TreeNode buildTreeChild(int[] inorder, int[] postorder,int left, int right) {
        if (left > right) return null;
        TreeNode root = new TreeNode(postorder[index]);
        int pivot = findIndex(inorder,postorder[index]);
        index--;
        root.right = buildTreeChild(inorder,postorder,pivot+1,right);
        root.left = buildTreeChild(inorder,postorder,left,pivot-1);
        return root;
    }

    private int findIndex(int[] inorder, int target) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == target) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        Test2 test2 = new Test2();
        test2.buildTree(inorder,postorder);
        System.out.println(666);
    }
}
